/*
 * Canvas Game Library
 * Module: AI
 * 
 * Copyright Chainsawrus Wreaks 2011
 * All rights reserved.
 */

/**
 * @fileOverview A collection of methods and utilities to bring AI algorithsm to your game!
 * 
 * @todo implement a A+ Heuristic algorithm
 */

/**
 * AI module namespace
 * @namespace CGL.ai
 */

CGL.ai = {};

CGL.ai.aStar = {
	Node : function() {
		node = {
			x : 0,
			y : 0,
			blocked : false,
			
			init : function(dx, dy) {
				this.x = dx;
				this.y = dy;
			},
			
			setBlocked : function(blocked) {
				this.blocked = blocked;
			}
		};
		return node;
	},
	
	Graph : function() {
		graph = {
			nodes : null,
			
			generateNodes : function(tileMap) {
				this.nodes = new Array(tileMap.getColumns());
				
				for(var i = 0; i < this.nodes.length; i++)
				{
					this.nodes[i] = new Array(tileMap.getRows());
				}
				
				for(var i = 0; i < this.nodes.length; i++)
				{
					for(var j = 0; j < this.nodes[i].length; j++)
					{
						this.nodes[i][j] = new CGL.ai.aStar.Node();
						this.nodes[i][j].init(i, j);
						
						if(tileMap.getTileId(i, j) == 1)
						{
							this.nodes[i][j].setBlocked(true);
						}
						else
						{
							this.nodes[i][j].setBlocked(false);
						}
					}
				}
			},
			
			isValidLocation : function(x, y) {
				if(x < 0 || y < 0 || x >= this.nodes.length || y >= this.nodes[0].length)
				{
					return false;
				}
				else if(this.nodes[x][y].blocked)
				{
					return false;
				}
				else
				{
					return true;
				}
			},
			
			getConnections : function(fromNode) {
				var connections = new Array();
				var tempCon;
				
				for(var i = -1; i < 2; i++)
				{
					for(var j = -1; j < 2; j++)
					{
						if(i == 0 && j == 0)
						{
							continue;
						}
						else if(this.isValidLocation(fromNode.x + i, fromNode.y + j))
						{
							tempCon = new CGL.ai.aStar.Connection();
							tempCon.setFromNode(fromNode);
							tempCon.setToNode(this.nodes[fromNode.x + i][fromNode.y + j]);
							tempCon.setCost(1);
							connections.push(tempCon);
						}
					}
				}
				return connections;
			}
		};
		return graph;
	},
	
	Connection : function() {
		conn = {
			cost : 0,
			fromNode : null,
			toNode : null,
			
			setCost : function(cost) {
				this.cost = cost;
			},
			
			getCost : function() {
				return this.cost;
			},
			
			setFromNode : function(node) {
				this.fromNode = node;
			},
			
			getFromNode : function() {
				return this.fromNode;
			},
			
			setToNode : function(node) {
				this.toNode = node;
			},
			
			getToNode : function() {
				return this.toNode;
			}
		};
		return conn;
	},
	
	NodeRecord : function() {
		nr = {
			node : new CGL.ai.aStar.Node(),
			connection : new CGL.ai.aStar.Connection(),
			costSoFar : 0,
			estimatedTotalCost : 0,
		
		
			setNode : function(node) {
				this.node = node;
			},
		
			getNode : function() {
				return this.node;
			},
		
			setConnection : function(connection) {
				this.connection = connection;
			},
		
			getConnection : function() {
				return this.connection;
			},
		
			setCostSoFar : function(csf) {
				this.costSoFar = csf;
			},
		
			getCostSoFar : function() {
				return this.costSoFar;
			},
		
			setEstimatedCost : function(ec) {
				this.estimatedCost = ec;
			},
		
			getEstimatedCost : function() {
				return this.estimatedCost;
			},
			
			setHeuristic : function(h) {
				this.heuristic = h;
			},
			
			getHeuristic : function() {
				return this.heuristic;
			},
			
			getCategory : function() {
				return this.category;
			},
			
			setCategory : function(cat) {
				this.category = cat;
			}
		};
		return nr;
	},
	
	Heuristic : function() {
		heuristic = {
			goalNode : null,
			
			init : function(goal) {
				this.goalNode = goal;
			},
			
			euclideanDist : function(current) {
				var dx, dy;
				
				dx = current.x - this.goalNode.x;
			    dy = current.y - this.goalNode.y;
			    
			    return Math.sqrt((dx*dx)+(dy*dy));
			},
		
			manhattanDist : function(current) {
				dx = Math.abs(this.goalNode.x - current.x);
			    dy = Math.abs(this.goalNode.y - current.y);
			    return dx+dy;
			}
		};
		return heuristic;
	},
	
	Step : function(dx, dy) {
		step = {
			x : dx,
			y : dy
		};
		return step;
	},
	
	NodeList : function() {
		nl = {
			list : new Array(),
			
			add : function(nodeRecord) {
				this.list.push(nodeRecord);
			},
		
			get : function(i) {
				return this.list[i];
			},
			
			getSmallest : function() {
				var smallest, current;
				
				smallest = this.list[0];
				
				for(var i = 0; i < this.list.length; i++)
				{
					current = this.list[i];
					if(current.getEstimatedCost() < smallest.getEstimatedCost())
					{
						smallest = current;
					}
				}
				return smallest;
			},
			
			contains : function(node) {
				var current;
				for(var i = 0; i < this.list.length; i++)
				{
					current = this.list[i].node;
					if(current.x == node.x && current.y == node.y)
					{
						return true;
					}
				}
				return false;
			},
			
			find : function(node) {
				var current;
				for(var i = 0; i < this.list.length; i++)
				{
					current = this.list[i].node;
					if(current.x == node.x && current.y == node.y)
					{
						return this.list[i];
					}
				}
			},
			
			remove : function(record) {
				var current;
				for(var i = 0; i < this.list.length; i++)
				{
					current = this.list[i];
					if(current.node.x == record.x && current.node.y == record.y)
					{
						this.list.splice(i, 1);
					}
				}
			},
			
			size : function() {
				return this.list.length;
			}
		};
		return nl;
	},
	
	PathfindAStar : function() {
		pas = {
			startRecord : new CGL.ai.aStar.NodeRecord(),
			open : new CGL.ai.aStar.NodeList(),
			closed : new CGL.ai.aStar.NodeList(),
			heuristic : new CGL.ai.aStar.Heuristic(),
			graph : new CGL.ai.aStar.Graph(),
			
			findPath : function(start, end, map) {
				var current, connections, endNode, endNodeCost, endNodeHeuristic, endNodeRecord, path;
				this.graph.generateNodes(map);
				this.heuristic.init(this.graph.nodes[end.x][end.y]);
				
				if(this.graph.nodes[end.x][end.y].blocked)
				{
					return null;
				}
				
				this.startRecord.node = this.graph.nodes[start.x][start.y];
				this.startRecord.setCostSoFar(0);
				this.startRecord.setEstimatedCost(this.heuristic.euclideanDist(this.startRecord.getNode()));
				//this.startRecord.setEstimatedCost(this.heuristic.manhattanDist(this.startRecord.getNode()));
				
				this.open.add(this.startRecord);
				
				while(this.open.size() > 0)
				{
					current = this.open.getSmallest();
					
					
					if(current.node.x == end.x && current.node.y == end.y)
					{
						break;
					}
					
					connections = this.graph.getConnections(current.getNode());
					
					for(var i = 0; i < connections.length; i++)
					{
						endNode = connections[i].getToNode();
						endNodeCost = current.getCostSoFar() + connections[i].getCost();
						
						if(this.closed.contains(endNode))
						{
							endNodeRecord = this.closed.find(endNode);
							
							if(endNodeRecord.getCostSoFar() <= endNodeCost)
							{
								continue;
							}
							this.closed.remove(endNodeRecord.getNode());
							
							endNodeHeuristic = endNodeRecord.getEstimatedCost() - endNodeRecord.getCostSoFar();
						}
						else if(this.open.contains(endNode))
						{
							endNodeRecord = this.open.find(endNode);
							
							if(endNodeRecord.getCostSoFar() <= endNodeCost)
							{
								continue;
							}
							
							endNodeHeuristic = endNodeRecord.getEstimatedCost() - endNodeRecord.getCostSoFar();
						}
						else
						{
							endNodeRecord = new CGL.ai.aStar.NodeRecord();
							endNodeRecord.setNode(endNode);
							
							endNodeHeuristic = this.heuristic.euclideanDist(endNode);
							//endNodeHeuristic = this.heuristic.manhattanDist(endNode);
						}
						
						endNodeRecord.setCostSoFar(endNodeCost);
						endNodeRecord.setConnection(connections[i]);
						endNodeRecord.setEstimatedCost(endNodeCost + endNodeHeuristic);
						
						if(!this.open.contains(endNode))
						{
							this.open.add(endNodeRecord);
						}	
					}
					this.open.remove(current.node);
					this.closed.add(current);
				}
				if(!(current.node.x == end.x && current.node.y == end.y))
				{
					return null;
				}
				else
				{
					path = new Array();
					while(!(current.node.x == start.x && current.node.y == start.y))
					{
						path.push(current.connection.getToNode());
						current = current.connection.getFromNode();
						current = this.closed.find(current);
					}
					return path;
				}
			}
		};
		return pas;
	}
};